// 真题描述：给你一个包含 n 个整数的数组 nums，
// 判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？
// 请你找出所有满足条件且不重复的三元组。

// 给定数组 nums = [-1, 0, 1, 2, -1, -4]， 满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]

/**
 * 双指针法用在涉及求和、比大小类的数组题目里时，大前提往往是：该数组必须有序。
 * 否则双指针根本无法帮助我们缩小定位的范围，压根没有意义。
 * 
 * 第一步是将数组排序
 * 
 * 然后对数组进行遍历，每次遍历到哪个数字，就固定哪个数字。然后把左指针指向该数字后面一个坑里的数字，
 * 把右指针指向数组末尾，让左右指针从起点开始，向中间前进
 * 
 * 每次指针移动一次位置，就计算一下两个指针指向数字之和加上固定的那个数之后，是否等于0。如果是，那么我们就得到了一个目标组合；否则，分两种情况来看：
 * 1. 相加之和大于0，说明右侧的数偏大了，右指针左移
 * 2. 相加之和小于0，说明左侧的数偏小了，左指针右移
 */

// 左右指针一起从两边往中间位置相互迫近，这样的特殊双指针形态，
// 被称为“对撞指针”。

const threeSum = function(nums) {
	// 用于存放结果数组
	let res = [];
	// 给 nums 排序
	nums = nums.sort((a, b) => {
		return a - b;
	});
	// 缓存数组长度
	const len = nums.length;
	// 注意我们遍历到倒数第三个数就足够了，因为左右指针会遍历后面两个数
	for (let i = 0; i < len - 2; i++) {
		// 左指针 j
		let j = i + 1;
		// 右指针k
		let k = len - 1;
		// 如果遇到重复的数字，则跳过
		if (i > 0 && nums[i] === nums[i - 1]) {
			continue;
		}
		while (j < k) {
			// 三数之和小于0，左指针前进
			if (nums[i] + nums[j] + nums[k] < 0) {
				j++;
				// 处理左指针元素重复的情况
				while (j < k && nums[j] === nums[j - 1]) {
					j++;
				}
			} else if (nums[i] + nums[j] + nums[k] > 0) {
				// 三数之和大于0，右指针后退
				k--;
				// 处理右指针元素重复的情况
				while (j < k && nums[k] === nums[k + 1]) {
					k--;
				}
			} else {
				// 得到目标数字组合，推入结果数组
				res.push([ nums[i], nums[j], nums[k] ]);
				// 左右指针一起前进
				j++;
				k--;
				// 若左指针元素重复，跳过
				while (j < k && nums[j] === nums[j - 1]) {
					j++;
				}
				// 若右指针元素重复，跳过
				while (j < k && nums[k] === nums[k + 1]) {
					k--;
				}
			}
		}
	}
	// 返回结果数组
	return res;
};

let nums = [-1, 0, 1, 2, -1, -4]
console.log(threeSum(nums));
